//从mXn网格的左上角走到右下角，求最短路径数
//递推公式：到达该点路径数等于到达该点左边路径数和到达上面的路径数
//于是得出要初始化的数组：上面一排和左边一排
#include <vector>
using std::vector;
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m,vector<int>(n));
    //初始化
    for(int i=0;i<m;i++) dp[i][0]=1;
    for(int i=0;i<n;i++) dp[0][i]=1;
    
    //二维两层循环
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}


//补充：也可以使用深度优先搜索，但会超时
int dfs(int i,int j,int m,int n){
    if(i>m||j>n) return 0;
    if(i==m&&j==n) return 1;
    return dfs(i+1,j,m,n)+dfs(i,j+1,m,n);
}
int uniquePaths(int m, int n) {
    return dfs(1,1,m,n);
}





//有障碍物的情景：
//有障碍物的格子dp数组为0，初始化时障碍物后面的格子也为0即可

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m=obstacleGrid.size();
    int n=obstacleGrid[0].size();
    vector<vector<int>> dp(m,vector<int>(n,0));
    for(int i=0;i<m&&obstacleGrid[i][0]!=1;i++) dp[i][0]=1; //前面没有障碍物才会走到这个格子
    for(int j=0;j<n&&obstacleGrid[0][j]!=1;j++) dp[0][j]=1; //前面没有障碍物才会走到这个格子
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(obstacleGrid[i][j]!=1) dp[i][j]=dp[i-1][j]+dp[i][j-1];       //有障碍物的格子dp为0，表示不会走到这个格子
        }
    }
    return dp[m-1][n-1];

}
